package LeetCode.month01.day02;



//寻找两个正序数组的中位数
public class No4 {

    public static void main(String[] args) {
        int[] a = {};
        int[] b = {1};
        System.out.println(findMedianSortedArrays(a, b));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //System.out.println(nums1);
        //System.out.println(nums2);
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2,nums1);
        }
        //System.out.println(nums1);
        //System.out.println(nums2);
        int left = 0, right = nums1.length;
        int m1=0,m2=0;
        while (left <= right) {
            int i = (left + right ) / 2;
            int j = (nums1.length + nums2.length + 1) / 2 - i;
            int n1leftmax = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int n1rightmin = (i == nums1.length ? Integer.MAX_VALUE : nums1[i]);
            int n2leftmax = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int n2rightmin = (j == nums2.length ? Integer.MAX_VALUE : nums2[j]);

            if(n1leftmax<=n2rightmin){
                m1 = Math.max(n1leftmax,n2leftmax);
                m2 = Math.min(n1rightmin,n2rightmin);
                left=i+1;
            }else{
                right = i-1;
            }
        }

        if ((nums1.length + nums2.length) % 2 == 0) return (m1+m2) / 2.0;
        else return m1;
    }
}
